home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / hash / shs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-25  |  11.8 KB  |  382 lines  |  [TEXT/R*ch]
  1. /* @(#)shs.c    10.1 3/25/94 08:03:59 */
  2. /*
  3.  * shs - NIST proposed Secure Hash Standard
  4.  *
  5.  * Written 2 September 1992, Peter C. Gutmann.
  6.  *
  7.  * This file was Modified/Re-written by:
  8.  *
  9.  *     Landon Curt Noll  (chongo@toad.com)    chongo <was here> /\../\
  10.  *
  11.  * This code has been placed in the public domain.  Please do not
  12.  * copyright this code.
  13.  *
  14.  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH  REGARD  TO
  15.  * THIS  SOFTWARE,  INCLUDING  ALL IMPLIED WARRANTIES OF MER-
  16.  * CHANTABILITY AND FITNESS.  IN NO EVENT SHALL  LANDON  CURT
  17.  * NOLL  BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  18.  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM  LOSS  OF
  19.  * USE,  DATA  OR  PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  20.  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR  IN
  21.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22.  *
  23.  * See shsdrvr.c for version and modification history.
  24.  */
  25.  
  26. #include <stdio.h>
  27. #include <string.h>
  28. #include "shs.h"
  29. #include "align.h"
  30. #include "endian.h"
  31.  
  32. char *shs_what="@(#)";    /* #(@) if checked in */
  33.  
  34. /*
  35.  * The SHS f()-functions.  The f1 and f3 functions can be optimized
  36.  * to save one boolean operation each - thanks to Rich Schroeppel,
  37.  * rcs@cs.arizona.edu for discovering this.
  38.  *
  39.  * f1: ((x&y) | (~x&z)) == (z ^ (x&(y^z)))
  40.  * f3: ((x&y) | (x&z) | (y&z)) == ((x&y) | (z&(x|y)))
  41.  */
  42. #define f1(x,y,z)       (z ^ (x&(y^z)))        /* Rounds  0-19 */
  43. #define f2(x,y,z)       (x^y^z)            /* Rounds 20-39 */
  44. #define f3(x,y,z)       ((x&y) | (z&(x|y)))    /* Rounds 40-59 */
  45. #define f4(x,y,z)       (x^y^z)            /* Rounds 60-79 */
  46.  
  47. /* The SHS Mysterious Constants */
  48. #define K1      0x5A827999L    /* Rounds  0-19 */
  49. #define K2      0x6ED9EBA1L    /* Rounds 20-39 */
  50. #define K3      0x8F1BBCDCL    /* Rounds 40-59 */
  51. #define K4      0xCA62C1D6L    /* Rounds 60-79 */
  52.  
  53. /* SHS initial values */
  54. #define h0init  0x67452301L
  55. #define h1init  0xEFCDAB89L
  56. #define h2init  0x98BADCFEL
  57. #define h3init  0x10325476L
  58. #define h4init  0xC3D2E1F0L
  59.  
  60. /* 32-bit rotate left - kludged with shifts */
  61. #define LEFT_ROT(X,n)  (((X)<<(n)) | ((X)>>(32-(n))))
  62.  
  63. /*
  64.  * The initial expanding function.  The hash function is defined over an
  65.  * 80-word expanded input array W, where the first 16 are copies of the input
  66.  * data, and the remaining 64 are defined by
  67.  *
  68.  *      W[i] = W[i-16] ^ W[i-14] ^ W[i-8] ^ W[i-3]
  69.  *
  70.  * This implementation generates these values on the fly in a circular
  71.  * buffer - thanks to Colin Plumb (colin@nyx10.cs.du.edu) for this
  72.  * optimization.
  73.  */
  74. #define exor(W,i) (W[i&15] ^= (W[(i-14)&15] ^ W[(i-8)&15] ^ W[(i-3)&15]))
  75.  
  76. /*
  77.  * The prototype SHS sub-round.  The fundamental sub-round is:
  78.  *
  79.  *      a' = e + LEFT_ROT(a,5) + f(b,c,d) + k + data;
  80.  *      b' = a;
  81.  *      c' = LEFT_ROT(b,30);
  82.  *      d' = c;
  83.  *      e' = d;
  84.  *
  85.  * but this is implemented by unrolling the loop 5 times and renaming the
  86.  * variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
  87.  * This code is then replicated 20 times for each of the 4 functions, using
  88.  * the next 20 values from the W[] array each time.
  89.  */
  90. #define subRound(a, b, c, d, e, f, k, data) \
  91.     (e += LEFT_ROT(a,5) + f(b,c,d) + k + data, b = LEFT_ROT(b,30))
  92.  
  93. /* forward declarations */
  94. static void shsTransform P((ULONG*, ULONG*));
  95. static ULONG in[SHS_CHUNKWORDS];
  96.  
  97.  
  98. /*
  99.  * shsInit - initialize the SHS state
  100.  */
  101. void
  102. shsInit(dig)
  103.     SHS_INFO *dig;
  104. {
  105.     /* Set the h-vars to their initial values */
  106.     dig->digest[0] = h0init;
  107.     dig->digest[1] = h1init;
  108.     dig->digest[2] = h2init;
  109.     dig->digest[3] = h3init;
  110.     dig->digest[4] = h4init;
  111.  
  112.     /* Initialise bit count */
  113.     dig->countLo = 0;
  114.     dig->countHi = 0;
  115.     dig->datalen = 0;
  116. }
  117.  
  118.  
  119. /*
  120.  * shsTransform - perform the SHS transformatio
  121.  *
  122.  * Note that this code, like MD5, seems to break some optimizing compilers.
  123.  * It may be necessary to split it into sections, eg based on the four
  124.  * subrounds.  One may also want to roll each subround into a loop.
  125.  */
  126. static void
  127. shsTransform(digest, W)
  128.     ULONG *digest;
  129.     ULONG *W;
  130. {
  131.     ULONG A, B, C, D, E;    /* Local vars */
  132.  
  133.     /* Set up first buffer and local data buffer */
  134.     A = digest[0];
  135.     B = digest[1];
  136.     C = digest[2];
  137.     D = digest[3];
  138.     E = digest[4];
  139.  
  140.     /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
  141.     subRound(A, B, C, D, E, f1, K1, W[ 0]);
  142.     subRound(E, A, B, C, D, f1, K1, W[ 1]);
  143.     subRound(D, E, A, B, C, f1, K1, W[ 2]);
  144.     subRound(C, D, E, A, B, f1, K1, W[ 3]);
  145.     subRound(B, C, D, E, A, f1, K1, W[ 4]);
  146.     subRound(A, B, C, D, E, f1, K1, W[ 5]);
  147.     subRound(E, A, B, C, D, f1, K1, W[ 6]);
  148.     subRound(D, E, A, B, C, f1, K1, W[ 7]);
  149.     subRound(C, D, E, A, B, f1, K1, W[ 8]);
  150.     subRound(B, C, D, E, A, f1, K1, W[ 9]);
  151.     subRound(A, B, C, D, E, f1, K1, W[10]);
  152.     subRound(E, A, B, C, D, f1, K1, W[11]);
  153.     subRound(D, E, A, B, C, f1, K1, W[12]);
  154.     subRound(C, D, E, A, B, f1, K1, W[13]);
  155.     subRound(B, C, D, E, A, f1, K1, W[14]);
  156.     subRound(A, B, C, D, E, f1, K1, W[15]);
  157.     subRound(E, A, B, C, D, f1, K1, exor(W,16));
  158.     subRound(D, E, A, B, C, f1, K1, exor(W,17));
  159.     subRound(C, D, E, A, B, f1, K1, exor(W,18));
  160.     subRound(B, C, D, E, A, f1, K1, exor(W,19));
  161.  
  162.     subRound(A, B, C, D, E, f2, K2, exor(W,20));
  163.     subRound(E, A, B, C, D, f2, K2, exor(W,21));
  164.     subRound(D, E, A, B, C, f2, K2, exor(W,22));
  165.     subRound(C, D, E, A, B, f2, K2, exor(W,23));
  166.     subRound(B, C, D, E, A, f2, K2, exor(W,24));
  167.     subRound(A, B, C, D, E, f2, K2, exor(W,25));
  168.     subRound(E, A, B, C, D, f2, K2, exor(W,26));
  169.     subRound(D, E, A, B, C, f2, K2, exor(W,27));
  170.     subRound(C, D, E, A, B, f2, K2, exor(W,28));
  171.     subRound(B, C, D, E, A, f2, K2, exor(W,29));
  172.     subRound(A, B, C, D, E, f2, K2, exor(W,30));
  173.     subRound(E, A, B, C, D, f2, K2, exor(W,31));
  174.     subRound(D, E, A, B, C, f2, K2, exor(W,32));
  175.     subRound(C, D, E, A, B, f2, K2, exor(W,33));
  176.     subRound(B, C, D, E, A, f2, K2, exor(W,34));
  177.     subRound(A, B, C, D, E, f2, K2, exor(W,35));
  178.     subRound(E, A, B, C, D, f2, K2, exor(W,36));
  179.     subRound(D, E, A, B, C, f2, K2, exor(W,37));
  180.     subRound(C, D, E, A, B, f2, K2, exor(W,38));
  181.     subRound(B, C, D, E, A, f2, K2, exor(W,39));
  182.  
  183.     subRound(A, B, C, D, E, f3, K3, exor(W,40));
  184.     subRound(E, A, B, C, D, f3, K3, exor(W,41));
  185.     subRound(D, E, A, B, C, f3, K3, exor(W,42));
  186.     subRound(C, D, E, A, B, f3, K3, exor(W,43));
  187.     subRound(B, C, D, E, A, f3, K3, exor(W,44));
  188.     subRound(A, B, C, D, E, f3, K3, exor(W,45));
  189.     subRound(E, A, B, C, D, f3, K3, exor(W,46));
  190.     subRound(D, E, A, B, C, f3, K3, exor(W,47));
  191.     subRound(C, D, E, A, B, f3, K3, exor(W,48));
  192.     subRound(B, C, D, E, A, f3, K3, exor(W,49));
  193.     subRound(A, B, C, D, E, f3, K3, exor(W,50));
  194.     subRound(E, A, B, C, D, f3, K3, exor(W,51));
  195.     subRound(D, E, A, B, C, f3, K3, exor(W,52));
  196.     subRound(C, D, E, A, B, f3, K3, exor(W,53));
  197.     subRound(B, C, D, E, A, f3, K3, exor(W,54));
  198.     subRound(A, B, C, D, E, f3, K3, exor(W,55));
  199.     subRound(E, A, B, C, D, f3, K3, exor(W,56));
  200.     subRound(D, E, A, B, C, f3, K3, exor(W,57));
  201.     subRound(C, D, E, A, B, f3, K3, exor(W,58));
  202.     subRound(B, C, D, E, A, f3, K3, exor(W,59));
  203.  
  204.     subRound(A, B, C, D, E, f4, K4, exor(W,60));
  205.     subRound(E, A, B, C, D, f4, K4, exor(W,61));
  206.     subRound(D, E, A, B, C, f4, K4, exor(W,62));
  207.     subRound(C, D, E, A, B, f4, K4, exor(W,63));
  208.     subRound(B, C, D, E, A, f4, K4, exor(W,64));
  209.     subRound(A, B, C, D, E, f4, K4, exor(W,65));
  210.     subRound(E, A, B, C, D, f4, K4, exor(W,66));
  211.     subRound(D, E, A, B, C, f4, K4, exor(W,67));
  212.     subRound(C, D, E, A, B, f4, K4, exor(W,68));
  213.     subRound(B, C, D, E, A, f4, K4, exor(W,69));
  214.     subRound(A, B, C, D, E, f4, K4, exor(W,70));
  215.     subRound(E, A, B, C, D, f4, K4, exor(W,71));
  216.     subRound(D, E, A, B, C, f4, K4, exor(W,72));
  217.     subRound(C, D, E, A, B, f4, K4, exor(W,73));
  218.     subRound(B, C, D, E, A, f4, K4, exor(W,74));
  219.     subRound(A, B, C, D, E, f4, K4, exor(W,75));
  220.     subRound(E, A, B, C, D, f4, K4, exor(W,76));
  221.     subRound(D, E, A, B, C, f4, K4, exor(W,77));
  222.     subRound(C, D, E, A, B, f4, K4, exor(W,78));
  223.     subRound(B, C, D, E, A, f4, K4, exor(W,79));
  224.  
  225.     /* Build message digest */
  226.     digest[0] += A;
  227.     digest[1] += B;
  228.     digest[2] += C;
  229.     digest[3] += D;
  230.     digest[4] += E;
  231. }
  232.  
  233.  
  234. /*
  235.  * shsUpdate - update SHS with arbitrary length data
  236.  *
  237.  * This code does not assume that the buffer size is a multiple of
  238.  * SHS_CHUNKSIZE bytes long.  This code handles partial chunk between
  239.  * calls to shsUpdate().
  240.  */
  241. void
  242. shsUpdate(dig, buffer, count)
  243.     SHS_INFO *dig;
  244.     BYTE *buffer;
  245.     ULONG count;
  246. {
  247.     ULONG datalen = dig->datalen;
  248.  
  249.     /*
  250.      * Catch the case of a non-empty data buffer
  251.      */
  252.     if (datalen > 0) {
  253.  
  254.     /* determine the size we need to copy */
  255.     ULONG cpylen = SHS_CHUNKSIZE - datalen;
  256.  
  257.     /* case: new data will not fill the buffer */
  258.     if (cpylen > count) {
  259.         memcpy((char *)dig->data+datalen, (char *)buffer, count);
  260.         dig->datalen = datalen+count;
  261.         return;
  262.  
  263.     /* case: buffer will be filled */
  264.     } else {
  265.         memcpy((char *)dig->data+datalen, (char *)buffer, cpylen);
  266.         SHS_TRANSFORM(dig, in, dig->data);
  267.         buffer += cpylen;
  268.         count -= cpylen;
  269.         dig->datalen = 0;
  270.     }
  271.     }
  272.  
  273.     /*
  274.      * Process data in SHS_CHUNKSIZE chunks
  275.      */
  276.     if (count >= SHS_CHUNKSIZE) {
  277.     shsfullUpdate(dig, buffer, count);
  278.     buffer += (count/SHS_CHUNKSIZE)*SHS_CHUNKSIZE;
  279.     count %= SHS_CHUNKSIZE;
  280.     }
  281.  
  282.     /*
  283.      * Handle any remaining bytes of data.
  284.      * This should only happen once on the final lot of data
  285.      */
  286.     if (count > 0) {
  287.     memcpy((char *)dig->data, (char *)buffer, count);
  288.     }
  289.     dig->datalen = count;
  290. }
  291.  
  292.  
  293. /*
  294.  * shsfullUpdate - update SHS with chunk multiple length data
  295.  *
  296.  * This function assumes that count is a multiple of SHS_CHUNKSIZE and that
  297.  * no partial chunk is left over from a previous call.
  298.  */
  299. void
  300. shsfullUpdate(dig, buffer, count)
  301.     SHS_INFO *dig;
  302.     BYTE *buffer;
  303.     ULONG count;
  304. {
  305.     /*
  306.      * Process data in SHS_CHUNKSIZE chunks
  307.      */
  308.     while (count >= SHS_CHUNKSIZE) {
  309. #if defined(MUST_ALIGN)
  310.     if ((long)buffer & (sizeof(ULONG)-1)) {
  311.         memcpy((char *)in, (char *)buffer, SHS_CHUNKSIZE);
  312.         SHS_TRANSFORM(dig, in, in);
  313.     } else {
  314.         SHS_TRANSFORM(dig, in, buffer);
  315.     }
  316. #else
  317.     SHS_TRANSFORM(dig, in, buffer);
  318. #endif
  319.     buffer += SHS_CHUNKSIZE;
  320.     count -= SHS_CHUNKSIZE;
  321.     }
  322. }
  323.  
  324.  
  325. /*
  326.  * shsFinal - perform final SHS transforms
  327.  *
  328.  * At this point we have less than a full chunk of data remaining
  329.  * (and possibly no data) in the shs state data buffer.
  330.  *
  331.  * First we append a final 0x80 byte.
  332.  *
  333.  * Next if we have more than 56 bytes, we will zero fill the remainder
  334.  * of the chunk, transform and then zero fill the first 56 bytes.
  335.  * If we have 56 or fewer bytes, we will zero fill out to the 56th
  336.  * chunk byte.  Regardless, we wind up with 56 bytes data.
  337.  *
  338.  * Finally we append the 64 bit length on to the 56 bytes of data
  339.  * remaining.  This final chunk is transformed.
  340.  */
  341. void
  342. shsFinal(dig)
  343.     SHS_INFO *dig;
  344. {
  345.     int count = dig->datalen;
  346.     ULONG lowBitcount = dig->countLo;
  347.     ULONG highBitcount = dig->countHi;
  348.  
  349.     /*
  350.      * Set the first char of padding to 0x80.
  351.      * This is safe since there is always at least one byte free
  352.      */
  353.     ((BYTE *)dig->data)[count++] = 0x80;
  354.  
  355.     /* Pad out to 56 mod SHS_CHUNKSIZE */
  356.     if (count > 56) {
  357.     /* Two lots of padding:  Pad the first chunk to SHS_CHUNKSIZE bytes */
  358.     memset((BYTE *)dig->data + count, 0, SHS_CHUNKSIZE - count);
  359.     SHS_TRANSFORM(dig, dig->data, dig->data);
  360.  
  361.     /* Now fill the next chunk with 56 bytes */
  362.     memset(dig->data, 0, 56);
  363.     } else {
  364.     /* Pad chunk to 56 bytes */
  365.     memset((BYTE *)dig->data + count, 0, 56 - count);
  366.     }
  367. #if BYTE_ORDER == LITTLE_ENDIAN
  368.     SWAP_BYTE_SEX(dig->data, dig->data);
  369. #endif
  370.  
  371.     /*
  372.      * Append length in bits and transform
  373.      *
  374.      * We assume that bit count is a multiple of 8 because we have
  375.      * only processed full bytes.
  376.      */
  377.     dig->data[SHS_HIGH] = (highBitcount << 3) | (lowBitcount >> 29);
  378.     dig->data[SHS_LOW] = (lowBitcount << 3);
  379.     shsTransform(dig->digest, dig->data);
  380.     dig->datalen = 0;
  381. }
  382.